The present invention relates to an image processing method, an image processor, an image forming apparatus and a memory product for reducing the number of gray levels in image data.
For example, when forming a pseudo-grayscale image including halftones by an image forming apparatus of binary output, it is necessary to perform a binarization process for reducing the number of gray levels to two levels while taking into account the grayscale reproducibility. As the binarization method, various methods have been used, such as a method in which a comparison with a threshold value is performed, a dithering method and an error diffusion method.
On the other hand, there is a method in which compressed image data is generated by coupling a first set of base coefficients in the frequency domain generated by forward transform (for example, discrete cosine transform) of image data and a second set of base coefficients corresponding to the frequency domain of predetermined halftone texture, and quantizing and entropy coding the coupled base coefficients (see, for example, Japanese Patent Application Laid-Open No. 2002-10085).
There is also a method in which compressed data is generated by dividing a grayscale image into a plurality of blocks, forming an average image based on the total of each block, predicting the original grayscale image by using the average image and a halftone screen matrix, generating a remainder image by comparing the predicted image and the original grayscale image, and compressing the generated remainder image and the average image (see, for example, Japanese Patent Application Laid-Open No. 2000-158879).
FIGS. 1A and 1B show examples of dither matrices used in a dithering method. Although a dithering method of binarization is explained as an example, the basic idea is also the same for a multi-valued case. In a dithering method, by using a 4×4 dither matrix in which threshold values of 0 to 15, for example, are set according to positions as shown in FIG. 1A, each pixel value in a 4×4 unit of 16-grayscale input image data is compared with a threshold value, and ON and OFF of each pixel is determined. In the case where the input image data is a 256-grayscale image, as shown in FIG. 1B, values obtained by multiplying the respective values in FIG. 1A by 16 are used as threshold values.
In the dithering method, however, since the binarization process is performed using dither matrices of the same pattern, regular periodic patterns tend to appear in the image on which the binarization process is performed, and there is the problem of repeated texture which is a characteristic of dithering.
An error diffusion method is a method in which binarization is performed while distributing an error caused during binarization of each pixel of the original image (hereinafter referred to as a quantization error) to neighboring pixels which have not yet been binarized . If a pixel to be binarized is denoted as an observed pixel, then the quantization error of the observed pixel is added to the value of each of the pixels surrounding the observed pixel which have not yet been binarized after giving a weight according to the relative position from the observed pixel.
FIG. 2 shows an example of a weighting coefficient matrix used in the error diffusion method. The example of FIG. 2 illustrates a 3×2 weighting coefficient matrix including the observed pixel (IX, IY) with the horizontal direction (processing direction) as the X direction and the perpendicular direction as the Y direction. The weighting coefficient matrix indicates the weighting coefficients of relative positions (lower left, lower, lower right, right positions) with respect to the observed pixel (IX, IY). For example, when the observed pixel (IX, IY) is compared with a threshold value, if the observed pixel (IX, IY) is larger than the threshold value, it is turned on, but, if the observed pixel (IX, IY) is smaller, it is turned off. Next, the difference (quantization error) between the determined pixel value of ON or OFF and the pixel value of the observed pixel (IX, IY) is distributed to the neighboring pixels which have not yet been binarized, based on the weighting coefficient matrix. However, since the pixel (IX−1, IY) on the left of the observed pixel (IX, IY) is quantized before the observed pixel (IX, IY), the quantization error is not distributed thereto.
For example, if the quantization error is Err, then Err×( 7/16), Err×( 1/16), Err×( 5/16), and Err×( 3/16) are distributed respectively to the right pixel (IX+1, IY), lower right pixel (IX+1, IY+1), lower pixel (IX, IY+1), and lower left pixel (IX−1, IY+1) with respect to the observed pixel (IX, IY).
An advantage of the error diffusion method over dithering or other methods is that better quality, such as less moiré pattern in the binarized image, is obtained by the distribution of quantization error to the neighboring pixels which have not yet been processed, based on the weighting coefficient matrix.
In the error diffusion method, however, since the error is diffused based on the same matrix for each pixel, there is a problem that a worm (portion where dots are partly connected) appears in a highlighted area, and a countermeasure such as, for example, adding noise to the threshold value during binarization has been taken (see, for example, “Threshold Adjusting Technique in Error Diffusion Method”, Toshiaki Kakutani, Journal of the Society of Electrophotography, 1998, Vol. 37, No. 2, p. 186-192).
In recent layers, with the improvement of the performance of image forming apparatuses such as ink jet printers, many image forming apparatus can provide multi-value output such as ternary output and quaternary output instead of binary output, and multi-valuing processing such as a multi-value error diffusion method, for example, is performed in these image forming apparatuses. The principle of the multi-value error diffusion method is basically the same as the error diffusion method of binarization, but differs in that input image data is quantized using two or more threshold values, and ternary or higher-value image data is outputted.
For example, in the case where error diffusion of quaternary output is performed on 256-grayscale image data with densities of 0 to 255, the output levels (values quantized by thresholding) can be 0, 85, 171 and 255, and the threshold values can be 42, 128 and 214. In this case, output levels are determined by successively comparing the pixel value of the observed pixel with the three threshold values. For instance, if an output level is smaller than the threshold value of 42, the output level is determined 0; and if an output level is smaller than the threshold value of 128, the output level is determined 85; otherwise the output level is determined 171 or 255 by comparison with the threshold value of 214.
However, in a multi-value image such as a quaternary image, since the dot patterns become uniform in an intermediate density region, there is a problem of tone gap (phenomenon in which gray levels change non-continuously). For example, when the output level is 0, 85, 171, or 255, a tone gap tends to occur in the vicinity of the intermediate density regions, 85 and 171, due to concentration of the same density. If quantization is performed with a plurality of threshold values, a tone gap definitely occurs. For instance, even in the case of binary output, a tone gap occurs in the vicinity of 0 or 255, but, in the case of multi-value output, since there is an output level of intermediate density which is easily noticed by human eyes, the tone gap in the intermediate density region is noticeable. It is difficult to perfectly prevent a tone gap in the intermediate density region by an algorism of performing quantization by appropriately selecting a plurality of threshold values for use in the intermediate density region.
In the methods disclosed in Japanese Patent Applications Laid-Open No. 2002-10085 and No. 2002-158879, data (frequency components) transformed into a predetermined halftone frequency domain is used, but, since predetermined halftone data is used, there is a problem such as occurrence of texture similarly to the above-mentioned error diffusion method or dithering method. In other words, the methods of Japanese Patent Applications Laid-Open No. 2002-10085 and No. 2002-158879 merely perform halftone processing in the frequency domain by using a method similar to the above-mentioned conventional methods.
Further, in the above-mentioned respective conventional techniques, since overlapping of dots of respective colors is not taken into account, not only dots of respective colors are formed on paper in an overlapped fashion, but also a pixel where a dot of any color is not formed tends to appear, and consequently there is a drawback that graininess becomes worse and causes a noisy rough image. In order to avoid this, for example, a dithering method needs to use different dither matrix for each color, or perform a special process such as determining the presence/absence of dot and shifting the dot position for each color, which causes in increase in the memory capacity and an increase in the amount of calculation, resulting in a problem of an increase in the calculation cost.